题意已经足够清楚了,我们直接说思路:
前置知识:
- 分块、莫队
- 离散化
- 一些奇奇怪怪的技巧
根据题意三段区间的数的总和为 ,其中 为三段区间内共有的数的个数。问题转化为求这个 的值。
容易想到,我们使用莫队维护查询的区间内每个数的个数。对于一次询问,我们将其拆成传统莫队的三个询问:,分别进行处理。我们要得到 ,需要得到这三个询问中有哪些数、分别几个,然后取它们的交集即可。
那么问题来了,这个交集(或三次询问)怎么求呢?注意一个数可能重复出现多次。我们考虑先将初始 数组进行离散化,只记录 数组每一个值对应排序好的数组的编号即可。这样,若干个相同的数便会留出若干个空着的编号,它们代表同一个值。然后使用这个离散化的对应关系用 bitset 存即可。
完结撒花!
等等,Ynoi 可不是这么简单就过去的。看一眼数据范围,。bitset 存不下!(笑容逐渐凝固)
没关系,我们可以把输入的查询分为若干组,每组 个数(当然更大也可以,不炸空间就没事),对于每一组分别进行处理即可。
小细节:莫队必须先进队再出队! 我因为一开始顺序搞混一直 RE,被卡了 1.5h!
真·完结撒花!
主要代码:
const ll N = 1e5+5, M = 2e4, K = M+5, SIZE = 320;
ll n, m, a[N], b[N], s[N];
ll vis[N], len[N];
bitset<N> cnts[K], u;
#define whichBlock(x) (\
(x-1)/SIZE+1\
)
struct Node {
ll l, r, id;
friend bool operator < (const Node &a, const Node &b) {
ll x = whichBlock(a.l), y = whichBlock(b.l);
if(x == y) return a.r < b.r;
return x < y;
}
}q[N];
void discretization() {
for(ll i=1;i<=n;i++) {
scanf("%lld", &a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
for(ll i=1;i<=n;i++) a[i] = ll(lower_bound(b+1, b+1+n, a[i]) - b);
}
void modify(ll x, ll y) {
ll z = a[x];
if(y == -1) u[z+(--s[z])] = 0;
else u[z+(s[z]++)] = 1;
}
void solve(ll op) {
assert(op > 0);
ll tot = 0;
memset(s, 0, sizeof(s));
for(ll i=1;i<=op;i++) {
vis[i] = len[i] = 0;
for(ll j=1;j<=3;j++) {
q[++tot].id = i;
scanf("%lld%lld", &q[tot].l, &q[tot].r);
len[i] += q[tot].r - q[tot].l + 1;
}
}
sort(q+1, q+1+tot);
ll l = 1, r = 0;
u.reset();
for(ll i=1;i<=tot;i++) {
while(l > q[i].l) modify(--l, 1);
while(r < q[i].r) modify(++r, 1);
while(l < q[i].l) modify(l++, -1);
while(r > q[i].r) modify(r--, -1);
if(vis[q[i].id]) cnts[q[i].id] &= u;
else cnts[q[i].id] = u;
vis[q[i].id] = 1;
}
for(ll i=1;i<=op;i++) printf("%lld\n", len[i]-3*(ll)cnts[i].count());
}